package vn.com.epi.algorithm.kdtree;

import java.util.Random;

public class KDTreeTest {
	
	static int n = 10000;
	static int d = 50;
	
	public static void test() {
		Random rand = new Random(System.currentTimeMillis());
		KDTree tree = new KDTree(d);
		int[][] key = new int[n][d];
		for (int i = 0; i < n; i++) {
			int k = 5 + rand.nextInt(10);
			boolean[] b = new boolean[d];
			for (int j = 0; j < d; j++) {
				b[j] = false;
				key[i][j] = 0;
			}
			for (int j = 0; j < k; j++) {
				int p;
				do {
					p = rand.nextInt(d);
				} while (b[p]);
				b[p] = true;
				key[i][p] = rand.nextInt(20);
			}
//			for (int j = 0; j < d; j++)
//				System.out.print(key[i][j] + "  ");
//			System.out.println();
			tree.insert(key[i], i);
		}
		
		for (int i = 0; i < n; i++) {
//			tree.delete(key[i]);
//			int j = (int) tree.nearest(key[i]);
//			HPoint x = new HPoint(key[i]);
//			HPoint y = new HPoint(key[j]);
//			System.out.println(i + " " + j + "\t" + (10000 - HPoint.eucdist(x, y)));
//			tree.insert(key[i], i);
			tree.nearest(key[i], 3);
		}
		
	}
	
	public static void main(String[] args) {
//		long start = System.currentTimeMillis();
//		test();
//		long end = System.currentTimeMillis();
//		System.out.println("Total time used: " + (end - start));
		KDTree tree = new KDTree(2);
		tree.insert(new int[] {1, 1}, 1); 
		tree.insert(new int[] {4, 8}, 2); 
		tree.insert(new int[] {2, 5}, 3); 
		tree.insert(new int[] {7, 10}, 4);
		tree.insert(new int[] {4, 10}, 5);
		int[] x = new int[] {4, 40};
		int[] y = new int[] {4, 10};
		HPoint pointX = new HPoint(x);
		HPoint pointY = new HPoint(y);
		Object[] index = tree.nearest(x, 2);
		for (int i = 0; i < index.length; i++) {			
			int p = (Integer) index[i];
			System.out.println(p);
		}
		System.out.println(HPoint.eucdist(pointX, pointY));
	}

}
